package leetcode.drawing;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

public class Path {
    public static void main(String[] args) {
        int n = 5;
        int[][] connections ={{1,0},{1,2},{3,2},{3,4}};
        minReorder(n,connections);
    }
    public static void minReorder(int n,int[][] connections) {
        HashMap<Integer, Node> hashMap = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> set1 = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        set1.add(0);
        for (int i = 1; i <n; i++) {
            set.add(i);
        }
        for (int i = 0; i < connections.length; i++) {
            if (!hashMap.containsKey(connections[i][0])) {
                Node node = new Node(connections[i][0]);
                node.set.add(connections[i][1]);
                hashMap.put(connections[i][0], node);
            } else {
                hashMap.get(connections[i][0]).set.add(connections[i][1]);
            }
            if (connections[i][1] == 0) {
                set1.add(connections[i][0]);
                set.remove(connections[i][0]);
                stack.push(connections[i][0]);
            }
        }
        int sum = 0;
        while (!set.isEmpty()){
            while (!stack.isEmpty()){
                int cur = stack.pop();
                if (hashMap.get(cur)!=null){
                    HashSet<Integer> hashSet = hashMap.get(cur).set;
                    for (int next : hashSet) {
                        if (!set1.contains(next)){
                            set1.add(next);
                            set.remove(next);
                            stack.push(cur);
                            stack.push(next);
                            sum++;
                            break;
                        }
                    }
                }
            }
            HashSet<Integer> integerHashSet = new HashSet<>();
            for (int num1 : set) {
                if (hashMap.containsKey(num1)){
                    HashSet<Integer> hashSet2 = hashMap.get(num1).set;
                    boolean flog = false;
                    for (int next2 : hashSet2) {
                        if (set1.contains(next2)){
                            set1.add(num1);
                            flog =true;
                            stack.add(num1);
                        }
                    }
                    if (!flog){
                        integerHashSet.add(num1);
                    }
                } else {
                    integerHashSet.add(num1);
                }

                set = integerHashSet;
            }
        }
        System.out.println(sum);
    }
    public static class Node{
       public int value;
       public HashSet<Integer> set;

        public Node(int value) {
            this.value = value;
            set = new HashSet<Integer>();
        }
    }
}
